









In a complete automaton $\mathcal{A}=(Q,A)$, for every letter $a\in A$ there is exactly one edge (transition) with label $a$ whose tail is
$q$; we denote the head of this edge by $q\cdot a$. Thus, each letter of the input alphabet defines a unary operation on the vertex set and
from the algebraic viewpoint, $\mathcal{A}$ is nothing but an algebra of type $(\underbrace{1,1,\dots,1}_{\text{$|A|$ times}})$ on the set
$Q$. This means that we may (and will) freely apply basic algebraic notions presented in Section~\ref{1.2} to complete automata. For
instance, a \emph{congruence}\index{congruence!on a complete automaton} on $\mathcal{A}$ is an equivalence $\pi$ on $Q$ that is stable
under the action of the letters in $A$: this means that $q\mathrel{\pi}q'$ implies $(q\cdot a)\mathrel{\pi}(q'\cdot a)$ for all $q,q'\in Q$
and for all $a\in A$. For $\pi$ being a congruence, $[q]_\pi$ is the $\pi$-class containing the vertex $q$. The \emph{quotient
automaton}\index{quotient automaton} $\mathcal{A}/\pi$ is defined in a  standard way: it has the set $Q/\pi$ of all $\pi$-class as the
vertex set and its transitions are of the form $[q]_\pi\xrightarrow{a}[q\cdot a]_\pi$ where $[q]_\pi$ runs over $Q/\pi$ and $a$ runs over
$A$. Fig.\,\ref{fig:quotient automaton} shows a 4-vertex automaton (in the left), a partition $\pi$ of its vertex set (denoted by the
dashed line) being a congruence, and the corresponding quotient automaton (in the right).
%\begin{figure}[ht]
%\begin{center}
%\unitlength=.7mm
%\begin{picture}(100,45.00)
%\node(A1)(5.00,10.00){1} \node(A3)(5.00,40.00){3}
%\node(A2)(35.00,10.00){2} \node(A4)(35.00,40.00){4}
%\drawedge(A1,A3){$a$} \drawedge[curvedepth=2](A2,A4){$a$}
%\drawloop[loopangle=180](A3){$a$} \drawloop[loopangle=0](A4){$a$}
%\drawedge(A3,A2){$b$} \drawedge[curvedepth=2](A4,A2){$b$}
%\drawedge(A2,A1){$b$} \drawloop[loopangle=180](A1){$b$}
%\node[Nframe=n](fakeleft)(-15,20){}
%\node[Nframe=n](fakeright)(55,20){$\pi$} \drawedge[dash={1.7
%0.5}{0.5},AHnb=0](fakeleft,fakeright){}
%\node(B1)(85.00,10.00){1,2} \node(B3)(85.00,40.00){3,4}
%\drawloop[loopangle=180](B1){$b$} \drawloop[loopangle=0](B3){$a$}
%\drawedge[curvedepth=2](B1,B3){$a$}
%\drawedge[curvedepth=2](B3,B1){$b$}
%\end{picture}
%\caption{A congruence and the corresponding quotient
%automaton}\label{fig:quotient automaton}
%\end{center}
%\end{figure}

\begin{example}\label{ee:Cayley} The labeled Cayley graph of every act (see Section \ref{ss:cayley}) with respect to any generating set $X$ is a complete automaton.
\end{example}

\begin{ex}\label{ex:act} Show that, conversely, every finite complete automaton $(Q,A)$ is the Cayley graph of a finite act of the free monoid $A^*$.
\end{ex}

\section{Synchronizing Automata}
\label{sec:synchronizing automata}

Let $(Q,A)$ be a complete automaton viewed as the Cayley graph of a free monoid $A^*$ acting on a finite set $Q$ (as in Exercise
\ref{ex:act}). Thus every word $w$ in $A^*$ corresponds to a function $q\mapsto q\cdot w$ from $Q$ to $Q$.
%In a complete automaton $\mathcal{A}=(Q,A)$, each pair $(q,w)$
%where $q$ is a vertex and $w$ is a word over $A$ determines a
%unique path starting at $q$: if $w=a_1a_2\cdots a_k$, then the
%path is $$q\xrightarrow{a_1} q\cdot a_1\xrightarrow{a_2}(q\cdot
%a_1)\cdot a_2\dots\xrightarrow{a_k} (\dots((q\cdot a_1)\cdot
%a_2)\dots)\cdot a_k.$$ We say that the path is labeled $w$. To
%simplify the notation, we write $q\cdot w$ for the final vertex of
%this path.
The automaton $(Q,A)$ is called \emph{synchronizing}\index{automaton!synchronizing} if there exists a word $w\in A^*$ such that the
corresponding function is a constant, that is all paths labeled by $w$ in $(Q,A)$ have the same final vertex. Any word $w$ with this
property is said to be a \emph{reset}\index{reset word} word for the automaton.

%\begin{figure}[ht]
%\unitlength=1mm
%\begin{center}
%\begin{picture}(20,40)(0,-10)
%\node(A)(0,20){0} \node(B)(20,20){1} \node(C)(20,0){2}
%\node(D)(0,0){3} \drawedge(A,B){$a,b$} \drawedge(B,C){$b$}
%\drawedge(C,D){$b$} \drawedge(D,A){$b$}
%\drawloop[loopangle=45](B){$a$} \drawloop[loopangle=-45](C){$a$}
%\drawloop[loopangle=-135](D){$a$}
%\end{picture}
%\caption{The automaton $\mathcal{C}_4$}\label{fig:C4}
%\end{center}
%\end{figure}
Fig.\,\ref{fig:C4} shows a \san\ with 4~vertices\footnote{Here and below we adopt the convention that edges bearing multiple labels
represent bunches of parallel edges. In particular, the edge $0\xrightarrow{a,b}1$ in Fig.\,\ref{fig:C4} represents the two parallel edges
$0\xrightarrow{a}1$ and $0\xrightarrow{b}1$.} denoted by $\mathcal{C}_4$. The reader can easily verify that the word $ab^3ab^3a$ resets the
automaton, the corresponding transformation takes every vertex to 1. With somewhat more effort one can also check that $ab^3ab^3a$ is the
shortest reset word for $\mathcal{C}_4$.

\begin{ex}
Let $G$ be a finite group,  $X$ be a generating set of $G$, $H$ be a subgroup of $G$. Show that the labeled Schreier graph of the subgroup
$H$ with respect to $X$ (see Section \ref{ss:cayley}) is not synchronizing. In particular labeled Cayley graphs of finite groups are not
synchronizing.
\end{ex}

The notion of a \san\ arose within the classic framework of Moore's ``Gedanken-experiments''~\cite{Moore:1956}. For Moore and his followers
finite automata served as a mathematical model of devices working in discrete mode, such as computers or relay control systems. This leads
to the following natural problem: how can we restore control over such a device if we do not know its current state but can observe outputs
produced by the device under various actions? Moore~\cite{Moore:1956} has shown that under certain conditions one can uniquely determine
the state at which the automaton arrives after a suitable sequence of actions (called an \emph{experiment}). Moore's experiments were
adaptive, that is, each next action was selected on the basis of the outputs caused by the previous actions. Ginsburg~\cite{Ginsburg:1958}
considered more restricted experiments. Ginsburg's experiment is just a fixed sequence of actions, that is, a word over the input alphabet;
thus, in Ginsburg's experiments outputs were only used for calculating the resulting state at the end of an experiment. From this, just one
further step was needed to come to the setting in which outputs were not used at all. It should be noted that this setting is by no means
artificial---there exist many practical situations when it is technically impossible to observe output signals. (Think of a satellite which
circles around the Moon and cannot be controlled from the Earth while ``behind'' the Moon.)

The original ``Gedanken-experiments'' motivation for studying \sa\ is still of importance, and reset words are frequently applied in
model-based testing of reactive systems, see \cite{Sandberg:2005} for a recent survey. Other motivations come from coding theory (see
\cite[Chapters~3 and~10]{Berstel&Perrin&Reutenauer:2009}) and robotics (see \cite[Section~1]{Volkov:2008}). Recently, it has been realized
that a notion that arose in studying of \emph{substitution systems} is also closely related to \sa. A
\emph{substitution}\index{substitution} on a finite alphabet $X$ is a map $\sigma:X\to X^+$; the substitution is said to be of
\emph{constant length}\index{substitution!of constant length} if all words $\sigma(x)$, $x\in X$, have the same length. One says that
$\sigma$ satisfies the \emph{coincidence condition}\index{coincidence condition} if there exist positive integers $m$ and $k$ such that all
words $\sigma^k(x)$ have the same letter in the $m$-th position. For an example, consider the substitution $\tau$ on $X=\{0,1,2\}$ defined
by $0\mapsto 11,\ 1\mapsto 12,\ 2\mapsto 20$. Calculating the iterations of $\tau$ up to $\tau^4$ (see Fig.\,\ref{fig:substituion}), we
observe that
\begin{figure}[h]
\begin{center}
$\begin{matrix}
0&\mapsto&11&\mapsto&1212&\mapsto&12201220&\mapsto&122020\mathbf{1}112202011\\
1&\mapsto&12&\mapsto&1220&\mapsto&12202011&\mapsto&122020\mathbf{1}120111212\\
2&\mapsto&20&\mapsto&2011&\mapsto&20111212&\mapsto&201112\mathbf{1}212201220
\end{matrix}$ \caption{A substitution satisfying the coincidence
condition} \label{fig:substituion}
\end{center}
\end{figure}
$\tau$ satisfies the coincidence condition (with $k=4$, $m=7$).

The importance of the coincidence condition comes from the fact (established by Dekking~\cite{Dekking:1978}) that it is this condition that
completely characterizes the constant length substitutions which give rise to dynamical systems measure-theoretically isomorphic to a
translation on a torus, see \cite[Chapter~7]{PytheasFogg:2002} for a survey. Observe that the coincidence condition is nothing but
synchronizability. Indeed, there is a straightforward bijection between complete automata and constant length substitutions. Each complete
automaton $\mathcal{A}=(Q,A)$ with $A=\{a_1,\dots,a_\ell\}$ defines a length $\ell$ substitution on $Q$ that maps every $q\in Q$ to the
word $(q\cdot a_1)\dots (q\cdot a_\ell)\in Q^+$. (For instance, the automaton $\mathcal{C}_4$ in Fig.\,\ref{fig:C4} induces the
substitution $0\mapsto 11,\ 1\mapsto 12,\ 2\mapsto 23,\ 3\mapsto 30$.) Conversely, each substitution $\sigma:X\to X^+$ such that all words
$\sigma(x)$, $x\in X$, have the same length $\ell$ gives rise to a complete automaton for which $X$ serves as the vertex set and which has
$\ell$ input letters $a_1,\dots,a_\ell$, say, acting on $X$ as follows: $x\cdot a_i$ is the symbol in the $i$-th position of the word
$\sigma(x)$. (For instance, the substitution $\tau$ considered in the previous paragraph defines the automaton shown in
Fig.\,\ref{fig:C3}.)
%\begin{figure}[ht]
%\unitlength=1mm
%\begin{center}
%\begin{picture}(20,35)(0,-10)
%\node(A)(10,20){0} \node(C)(20,0){1} \node(D)(0,0){2}
%\drawedge(A,C){$a_1,a_2$} \drawedge(C,D){$a_2$}
%\drawedge(D,A){$a_2$} \drawloop[loopangle=-45](C){$a_1$}
%\drawloop[loopangle=-135](D){$a_1$}
%\end{picture}
%\caption{The automaton induced by the substitution\protect\\
%$0\mapsto 11,\ 1\mapsto 12,\ 2\mapsto 20$}\label{fig:C3}
%\end{center}
%\end{figure}
It is clear that under the described bijection substitutions satisfying the coincidence condition correspond precisely to \sa, and
moreover, given a substitution, the number of iterations at which the coincidence first occurs is equal to the minimum length of \sw\ for
the corresponding automaton.





\section{The \v{C}ern\'{y} conjecture}
\label{sec:Cerny conjecture}

A very natural question to ask is the following: \emph{given a positive integer $n$, how long can \sws\ be for \sa\ with $n$ vertices?}
\v{C}ern\'{y}~\cite{Cerny:1964} found a lower bound by constructing, for each $n>1$, a \san\ $\mathcal{C}_n$\index{automaton!\v{C}ern\'{y}}
with $n$ vertices and 2 input letters whose shortest \sw\ has length $(n-1)^2$. We assume that the vertex set of $\mathcal{C}_n$ is
$Q=\{0,1,2,\dots,n-1\}$ and the input letters are $a$ and $b$, subject to the following action on $Q$:
\begin{displaymath}
i\cdot a=\begin{cases}
i &\text{if } i>0,\\
1 &\text{if } i=0;
\end{cases}\quad
i\cdot b=i+1\!\!\pmod{n}.
\end{displaymath}
Our first example of \san\ (see Figure~\ref{fig:C4}) is, in fact, $\mathcal{C}_4$. A generic automaton $\mathcal{C}_n$ is shown in
Figure~\ref{fig:cerny-n} on the left.

%\begin{figure}[ht]
%\begin{center}
%\unitlength .5mm
%\begin{picture}(72,86)(30,-86)
%\gasset{Nw=18,Nh=18,Nmr=9,loopdiam=12} \node(n0)(36.0,-16.0){1}
%\node(n1)(4.0,-40.0){$0$} \node(n2)(68.0,-40.0){2}
%\node(n3)(16.0,-72.0){$n{-}1$} \node(n4)(56.0,-72.0){3}
%\drawedge[ELdist=2.0](n1,n0){$a,b$}
%\drawedge[ELdist=1.5](n2,n4){$b$}
%\drawedge[ELdist=1.7](n0,n2){$b$}
%\drawedge[ELdist=1.7](n3,n1){$b$}
%\drawloop[ELdist=1.5,loopangle=30](n2){$a$}
%\drawloop[ELdist=2.4,loopangle=-30](n4){$a$}
%\drawloop[ELdist=1.5,loopangle=90](n0){$a$}
%\drawloop[ELdist=1.5,loopangle=210](n3){$a$} \put(31,-73){$\dots$}
%\end{picture}
%\begin{picture}(72,76)(-30,-86)
%\gasset{Nw=18,Nh=18,Nmr=10} \node(n0)(36.0,-16.0){1}
%\node(n1)(4.0,-40.0){$0$} \node(n2)(68.0,-40.0){2}
%\node(n3)(16.0,-72.0){$n{-}1$} \node(n4)(56.0,-72.0){3}
%\drawedge[ELdist=2.0](n1,n0){$b$}
%\drawedge[ELdist=1.5](n2,n4){$b,c$}
%\drawedge[ELdist=1.7](n0,n2){$b,c$}
%\drawedge[ELdist=1.7](n3,n1){$b,c$}
%\drawedge[ELdist=2.0](n1,n2){$c$} \put(31,-73){$\dots$}
%\end{picture}
%\end{center}
%\caption{The automaton $\mathcal{C}_n$ and the automaton $\mathcal{W}_n$
%induced by the actions of $b$ and $c=ab$}\label{fig:cerny-n}
%\end{figure}

It is easy to see that the word $(ab^{n-1})^{n-2}a$ of length $n(n-2)+1=(n-1)^2$ resets $\mathcal{C}_n$.
\begin{proposition}[{\mdseries\cite[Lemma~1]{Cerny:1964}}]
\label{prop:cerny} Any \sw\ for $\mathcal{C}_n$ has length at least $(n-1)^2$.
\end{proposition}
There are several nice proofs for this result. Here we present a recent proof from~\cite{Ananichev&Gusev&Volkov:2010}; it is based on a
transparent idea and reveals an interesting connection between \v{C}ern\'{y}'s automata $\mathcal{C}_n$ and an extremal series of graphs
discovered in Wielandt's classic paper~\cite{Wielandt:1950}.

\begin{proof}[Proof of Proposition~\ref{prop:cerny}]
Let $w$ be a \sw\ of minimum length for $\mathcal{C}_n$. Since the letter $b$ acts on $Q$ as a cyclic permutation, the word $w$ cannot end
with $b$. (Otherwise removing the last letter gives a shorter \sw.) Thus, $w = w'a$ for some $w'\in\{a,b\}^*$ such that the image of $Q$
under the action of $w'$ is precisely the set $\{0,1\}$.

Since the letter $a$ fixes each vertex in its image $\{1,2,\dots,n-1\}$, every occurrence of $a$ in $w$ except the last one is followed by
an occurrence of $b$. (Otherwise $a^2$ occurs in $w$ as a factor and reducing this factor to just $a$ results in a shorter \sw.) Therefore,
if we let $c=ab$, then the word $w'$ can be rewritten into a word $v$ over the alphabet $\{b,c\}$. The actions of $b$ and $c$ induce a new
automaton on the vertex set $Q$; we denote this induced automaton (shown in Figure~\ref{fig:cerny-n} on the right) by $\mathcal{W}_n$.
Since $w'$ and $v$ act on $Q$ in the same way, the word $vc$ is a \sw\ for $\mathcal{W}_n$ and brings the automaton to the vertex~2.

If $u\in\{b,c\}^*$, the word $uvc$ also is a \sw\ for $\mathcal{W}_n$ and it also brings the automaton to~2. Hence, for every
$\ell\ge|vc|$, there is a path of length $\ell$ in $\mathcal{W}_n$ from any given vertex $i$ to~2. In particular, setting $i=2$, we
conclude that for every $\ell\ge|vc|$ there is a cycle of length $\ell$ in $\mathcal{W}_n$. The underlying graph of $\mathcal{W}_n$ has
simple cycles only of two lengths: $n$ and $n-1$. Each cycle of $\mathcal{W}_n$ must consist of simple cycles of these two lengths whence
each number $\ell\ge|w|$ must be expressible as a non-negative integer combination of $n$ and $n-1$. Here we invoke the following
well-known and elementary result from arithmetics:

\begin{lemma}[{\mdseries\cite[Theorem 2.1.1]{RamirezAlfonsin:2005}}]
\label{lemma:sylvester} If $k_1,k_2$ are relatively prime positive integers, then $k_1k_2-k_1-k_2$ is the largest integer that is not
expressible as a non-negative integer combination of $k_1$ and $k_2$.
\end{lemma}

\begin{ex}
Prove Lemma~\ref{lemma:sylvester}.
\end{ex}

Lemma~\ref{lemma:sylvester} implies that $|vc|>n(n-1)-n-(n-1)=n^2-3n+1$. Suppose that $|vc|=n^2-3n+2$. Then there should be a path of this
length from the vertex~1 to the vertex~2. Every outgoing edge of~1 leads to~2, and thus, in the path it must be followed by a cycle of
length $n^2-3n+1$. No cycle of such length may exist by Lemma~\ref{lemma:sylvester}. Hence $|vc|\ge n^2-3n+3$.

Since the action of $b$ on any set $S$ of vertices cannot change the cardinality of $S$ and the action of $c$ can decrease the cardinality
by~1 at most, the word $vc$ must contain at least $n-1$ occurrences of $c$. Hence the length of $v$ over $\{b,c\}$ is at least $n^2-3n+2$
and $v$ contain at least $n-2$ occurrences of $c$. Since each occurrence of $c$ in $v$ corresponds to an occurrence of the subword $ab$ in
$w'$, we conclude that the length of $w'$ over $\{a,b\}$ is at least $n^2-3n+2+n-2=n^2-2n$. Thus, $|w|=|w'a|\ge n^2-2n+1=(n-1)^2$.
\end{proof}

If we define the \emph{\v{C}ern\'{y} function}\index{Cerny@\v{C}ern\'{y} function} $\mathfrak{C}(n)$ as the maximum length of shortest
reset words for \sa\ with $n$ vertices, the above property of the series $\{\mathcal{C}_{n}\}$, $n=2,3,\dotsc$, yields the inequality
$\mathfrak{C}(n)\ge(n-1)^2$. The \emph{\v{C}ern\'{y} conjecture}\index{Cerny@\v{C}ern\'{y} conjecture} is the claim that the equality
$\mathfrak{C}(n)=(n-1)^2$ holds true.

In the literature, one often refers to \v{C}ern\'{y}'s paper~\cite{Cerny:1964} as the source of the \v{C}ern\'{y} conjecture. In fact, the
conjecture was not yet formulated in that paper. There \v{C}ern\'{y} only observed that $(n-1)^2\le \mathfrak{C}(n)\le 2^n-n-1$ and
concluded the paper with the following remark:
\begin{quote}
``The difference between the bounds increases rapidly and it is necessary to sharpen them. One can expect an improvement mainly for the
upper bound.''
\end{quote}
The conjecture in its present-day form was formulated a bit later, after the expectation in the above quotation was confirmed by
\cite{Starke:1966}. (Namely, Starke improved the upper bound from~\cite{Cerny:1964} to $1+\frac{n(n-1)(n-2)}2$, which was the first
polynomial upper bound for $\mathfrak{C}(n)$.) \v{C}ern\'{y} explicitly stated the conjecture $\mathfrak{C}(n)=(n-1)^2$ in his talks in the
second half of the 1960s; in print the conjecture first appeared in~\cite{Cerny&Piricka&Rosenauerova:1971}.

The best upper bound for the \v{C}ern\'{y} function achieved so far guarantees that for every \san\ with $n$ vertices there exists a reset
word of length $\frac{n^3-n}6$. This bound was obtained by Pin~\cite{Pin:1983} modulo a conjecture from combinatorics on finite sets that
was then confirmed by Frankl~\cite{Frankl:1982}.

\section{The Road Coloring Problem}
\label{sec:rcp}

Recall that automata obtained from a graph $\Gamma$ by labeling its edges with letters from some alphabet are called \emph{colorings} of
$\Gamma$. A graph $\Gamma$ in which each vertex has the same out-degree (say, $k$) is called a \emph{graph of constant
out-degree}\index{graph!of constant out-degree} and the number $k$ is referred to as the out-degree of $\Gamma$. If we take an alphabet $A$
whose of size is equal to the out-degree of $\Gamma$, then we can label the edges of $\Gamma$ by letters of $A$ such that the resulting
automaton will be complete. In this section we consider only graphs of constant out-degree and their colorings being complete automata.

Given a graph, it is natural to ask under which conditions it admits a coloring satisfying some ``good'' properties. In this section we
analyze the so-called \emph{Road Coloring Problem}\index{Road Coloring Problem} that is certainly the most famous question within this
framework. The Road Coloring Problem asks under which conditions graphs of constant out-degree admit a synchronizing coloring.

The problem was explicitly stated by Adler, Goodwyn and Weiss~\cite{Adler&Goodwyn&Weiss:1977} in 1977; in an implicit form it was present
already in an earlier memoir by Adler and Weiss~\cite{Adler&Weiss:1970}. Adler, Goodwyn and Weiss considered only \scn\ graphs; as we shall
see below this is quite a natural assumption since the general case easily reduces to the case of \scn\ graphs. The name of the problem
suggested in~\cite{Adler&Goodwyn&Weiss:1977} comes from the following interpretation. In a \san\ $\mathcal{A}=(Q,A)$ whose underlying graph
is \scn, one can assign to every vertex $q\in Q$  an instruction (a \sw) $w_q$ such that following $w_q$ one will surely arrive at $q$ from
any initial vertex. (Indeed, for this one should first follow an arbitrary \sw\ leading to some vertex $p$, say, and then follow a word
that labels a path connecting $p$ and $q$---such a path exists because of strong connectivity.) Thus, in order to help a traveler lost on a
given \scn\ graph $\Gamma$ of constant out-degree to find his/her way from wherever he/she could be, we should if possible color (that is,
label) the edges of $\Gamma$ such that $\Gamma$ becomes a \san\ and then tell the traveler the magic sequence of colors representing a \sw\
leading to the traveler's destination.

\begin{example}
\label{examp:totalsync} The graph in Fig.\,\ref{fig:two colorings} admits a synchronizing coloring---in fact, each of the two its colorings
shown in Fig.\,\ref{fig:two colorings} is synchronizing. Moreover, it can be shown that \textbf{every} coloring of the graph is
synchronizing.
\end{example}

\begin{ex}
In contrast to Example~\ref{examp:totalsync}, the graph shown in Fig.\,\ref{fig:gusev} admits both synchronizing and non-synchronizing
colorings. Find such colorings, and for the synchronizing one, construct a \sw\ of minimum length that leads to the vertex~$0$.
%\begin{figure}[h]
%  \begin{center}
%    \unitlength=4pt
%    \begin{picture}(72, 30)(0,-7)
%    \gasset{Nw=6,Nh=6,Nmr=3}
%    \thinlines
%    \node(A0)(0,7.5){$0$}
%    \node(A1)(12,15){}
%    \node(A2)(12,0){}
%    \node(A3)(27,15){}
%    \node(A4)(27,0){}
%    \node(A5)(42,15){}
%    \node(A6)(42,0){}
%    \node(An3)(57,15){}
%    \node(An2)(57,0){}
%    \node(An1)(72,15){}
%    \node(An)(72,0){}
%    \drawedge(A0,A1){}
%    \drawedge(A0,A2){}
%    \drawedge(A1,A3){}
%    \drawedge(A1,A4){}
%    \drawedge(A2,A3){}
%    \drawedge(A2,A4){}
%    \drawedge(A3,A5){}
%    \drawedge(A3,A6){}
%    \drawedge(A4,A5){}
%    \drawedge(A4,A6){}
%    \drawedge(A6,An3){}
%    \drawedge(A6,An2){}
%    \drawedge(A5,An3){}
%    \drawedge(A5,An2){}
%    \drawedge(An3,An1){}
%    \drawedge(An3,An){}
%    \drawedge(An2,An1){}
%    \drawedge(An2,An){}
%    \drawcurve(70,17)(60,19)(27,19)(14.2,17)
%    \drawcurve(71.5,18)(60,22)(27,23)(10,20)(0,10.8)
%    \drawcurve(70,-2)(60,-4)(27,-4)(14.2,-2)
%    \drawcurve(71.5,-3)(60,-7)(27,-7)(10,-5)(0,4.2)
%    \end{picture}
%    \caption{Graph admitting a synchronizing coloring}\label{fig:gusev}
%  \end{center}
%\end{figure}
\end{ex}

\begin{ex}
1. Find a synchronizing coloring of the Cayley graph of the group of all permutations of $\{1,2,3\}$ with respect to the generating set
consisting of permutations $1\to 2, 2\to 1, 3\to 3$ and $1\to 2, 2\to 3, 3\to 1$.

2. Do the same for the Cayley graph of the Dihedral group $D_{2n}$ for odd $n$ with respect to its generating set introduced in
Exercise~\ref{exer:dihedral}.

3. Is there a synchronizing coloring for the Cayley graph of $D_{2n}$ (with respect to the generating set from
Exercise~\ref{exer:dihedral}) if $n$ is even?
\end{ex}

The original motivation in~\cite{Adler&Weiss:1970,Adler&Goodwyn&Weiss:1977} that came from symbolic dynamics will be explained in the next
section. However, the Road Coloring Problem is quite natural also from the viewpoint of the ``reverse engineering'' of \sa: we aim to
relate geometry properties of graphs to combinatorial properties of automata built on those graphs.

The following necessary condition was found in~\cite{Adler&Goodwyn&Weiss:1977}:
\begin{proposition}
\label{prop:primitivity} If a \scn\ graph $\Gamma=(V,E)$ admits a synchronizing coloring, then the g.c.d. of lengths of all cycles in
$\Gamma$ is equal to $1$.
\end{proposition}

\begin{proof}
Arguing by contradiction, let $k>1$ be a common divisor of lengths of the cycles in $\Gamma$. Take a~vertex $v_0\in V$ and, for
$i=0,1,\dots,k-1$, let
$$V_i=\{v\in V\mid \text{there exists a path from } v_0 \text{ to } v \text{ of length }
i\!\!\pmod{k}\}.$$ Clearly, $V=\bigcup\limits_{i=0}^{k-1} V_i$. We claim that $V_i\cap V_j=\varnothing$ if $i\ne j$.

Let $v\in V_i\cap V_j$ where $i\ne j$. This means that in $\Gamma$ there are two paths from $v_0$ to $v$: of length $\ell\equiv
i\!\!\pmod{k}$ and of length $m\equiv j\!\!\pmod{k}$. Since $\Gamma$ is \scn, there exists also a path from $v$ to $v_0$ of length $n$,
say. Combining it with each of the two paths above we get a cycle of length $\ell+n$ and a cycle of length $m+n$. Since $k$ divides the
length of any cycle in $\Gamma$, we have $\ell+n\equiv i+n\equiv 0\!\!\pmod{k}$ and $m+n\equiv j+n\equiv 0\!\!\pmod{k}$, whence $i\equiv
j\!\!\pmod{k}$, a contradiction.

Thus, $V$ is a disjoint union of $V_0,V_1,\dots,V_{k-1}$, and by the definition each edge in $\Gamma$ leads from $V_i$ to
$V_{i+1\!\!\pmod{k}}$. Then $\Gamma$ definitely cannot be converted into a \san\ by any coloring of its edges: no paths of the same length
$\ell$ originated in $V_0$ and $V_1$ can terminate in the same vertex because they end in $V_{\ell\!\!\pmod{k}}$ and in
$V_{\ell+1\!\!\pmod{k}}$ respectively.
\end{proof}

Graphs satisfying the conclusion of Proposition~\ref{prop:primitivity} are called \emph{primitive}\footnote{In the literature, such graphs
are sometimes called \emph{aperiodic}. The term ``primitive'' comes from the notion of a primitive matrix in the Perron-Frobenius theory of
non-negative matrices: it is known (and easy to see) that a graph is primitive if and only if so is its incidence
matrix.}.\index{graph!primitive} Adler, Goodwyn and Weiss~\cite{Adler&Goodwyn&Weiss:1977} conjectured that primitivity is not only
necessary for a graph to have a synchronizing coloring but also sufficient. In other word, they suggested the following \emph{Road Coloring
Conjecture}\index{Road Coloring Conjecture}: every \scn\ primitive graph with constant out-degree admits a synchronizing coloring.

The Road Coloring Conjecture has attracted much attention. There were several interesting partial results, and finally the problem was
solved (in the affirmative) in August 2007 by Trakhtman~\cite{Trahtman:2009}. We present Trakhtman's solution here.

The first step was done by Culik, Karhum\"aki and Kari~\cite{Culik&Karhumaki&Kari:2002}. They defined the \emph{confluence
relation}\index{confluence relation} $\sim$ on an automaton $Q$ as follows:
$$q\sim q' \Longleftrightarrow\forall u\in A^*\ \exists v\in A^*\ q\cdot uv=q'\cdot uv.$$
Any pair $(q,q')$ such that $q\ne q'$ and $q\sim q'$ is called \emph{confluent}\index{confluent pair}.\footnote{It is somewhat similar to
the notion of confluence for rewriting systems, see \ref{ss:conf}.}

%A coloring of a graph with constant outdegree is said to be
%\emph{confluent} if the resulting automaton has a confluent
%pair.\index{coloring (of a graph)!confluent}

The following lemma is obvious.

\begin{lemma} The confluence relation is an equivalent relation. In fact it is a congruence relation on the automaton considered as an algebra with signature $(1,...,1)$.
\label{l:cr}
\end{lemma}


\begin{proposition}[Culik, Karhum\"aki and
Kari~\cite{Culik&Karhumaki&Kari:2002}] \label{prop:ckk} If every \scn\ primitive graph with constant out-degree and more than one vertex
has a coloring with a confluent pair of vertices, then the Road Coloring Conjecture is true.
\end{proposition}

\begin{proof}
Let $\Gamma$ be a \scn\ primitive graph with constant out-degree. We show that $\Gamma$ has a synchronizing coloring by induction on the
number of vertices in $\Gamma$. If $\Gamma$ has only one vertex, there is nothing to prove. If $\Gamma$ has more than one vertex, then, by
the assumption, it admits a coloring with a confluent pair of vertices by the letters of some alphabet $A$. Let $\mathcal{A}$ be the
automaton resulting from this coloring. By Lemma \ref{l:cr}, confluence relation is a congruence of $\mathcal{A}$. Since the relation is
non-trivial, the quotient automaton $\mathcal{A}/\!{\sim}$ has fewer vertices than $A$. Since the quotient graph of every \scn graph is
again \scn (check it!),  the underlying graph $\Gamma/\!\!\!\sim$ of $\mathcal{A}/\!{\sim}$ is \scn. Moreover, since each cycle in $\Gamma$
induces a cycle of the same length in $\Gamma/\!\!\!\sim$, the latter graph is primitive as well. Therefore, by the induction assumption,
the graph $\Gamma/\!\!\!\sim$ admits a synchronizing coloring.

We lift this coloring to a coloring of $\Gamma$ in the following natural way. If $p\xrightarrow{} q$ is an edge in $\Gamma$, let $[p], [q]$
denote the $\sim$-congruence classes of $p,q$. If in the new coloring of the quotient graph, the edge $[p]\xrightarrow{ }[q]$ has color
$a'$, then we recolor $p\xrightarrow{ }q$ in the color  $a'$ as well.
%A crucial feature of this recoloring procedure is that it
%is consistent with the confluence relation $\sim$ in the following sense.
%Suppose $p\xrightarrow{a}q$ and $p'\xrightarrow{a}q'$ are two transitions with
%the same label in $\mathcal{A}$ such that $p\sim p'$ and $q\sim q'$. Then
%$[p]=[p']$, $[q]=[q']$ and the two transitions induce the same transition
%$[p]\xrightarrow{a}[q]$ in $\mathcal{A}/\!{\sim}$. If it is being recolored to
%$[p]\xrightarrow{a'}[q]$ for some $a'\in A$, then the two transitions are being
%changed in the same way such that the resulting transitions
%$p\xrightarrow{a'}q$ and $p'\xrightarrow{a'}q'$ still have a common label.

Let $\mathcal{A'}$ be the automaton resulting from the lifted coloring; we will show that $\mathcal{A'}$ is synchronizing. Let $w$ be a
\sw\ for the synchronizing coloring of $\Gamma/\!\!\!\sim$. Then $w$ maps the set of all vertices to a set $S$ that is contained in a
single congruence class of $\sim$. List all pairs of distinct vertices of $S$ in some (arbitrary) order: $(x_1,y_1),...,(x_n,y_n)$. By the
definition of $\sim$, there exist words $v_1,v_2,...,v_n$ such that $$x_1\cdot v_1=y_1\cdot v_1,$$ $$(x_2\cdot v_1)\cdot v_2=(y_2\cdot
v_1)\cdot v_2,...,$$ $$(...(x_n\cdot v_1)...\cdot v_n)=(...(y_n\cdot v_1)...\cdot v_n).$$ Therefore the word $wv_1v_2...v_n$ is a \sw\ for
$A'$.
\end{proof}

Proposition~\ref{prop:ckk} ``localizes'' the initial task: while synchronization is a ``global'' property in which all vertices are
involved, confluence refers only to a pair of vertices. We need a further localization that allows us to concentrate on the action of a
single letter. For this, we need some auxiliary notions and results.

Let $\mathcal{A}=(Q,A)$ be a complete automaton. A pair $(p,q)$ of distinct vertices is \emph{compressible} if $p\cdot w=q\cdot w$ for some
$w\in A^*$; otherwise it is\index{compressible pair} \emph{incompressible}.\index{incompressible pair} A subset $P\subseteq Q$ is said to
be \emph{compressible}\index{compressible set} if $P$ contains a compressible pair and to be \emph{incompressible} if every pair of
distinct vertices in $P$ is incompressible.\index{incompressible set} Clearly, if $P$ is incompressible, then for every word $u\in A^*$,
the set $P\cdot u=\{p\cdot u\mid p\in P\}$ also is incompressible and $|P|=|P\cdot u|$.

\begin{lemma}
\label{lemma:maximal incompressible} Let $P$ be an incompressible set of maximum size in a complete automaton $\mathcal{A}=(Q,A)$. Suppose
that there exist a word $w\in A^*$ and a vertex $q\in P$ such that $q\cdot w\ne q$ but $p\cdot w=p$ for all $p\in P'=P\setminus\{q\}$. Then
the pair $(q,q\cdot w)$ is confluent.
\end{lemma}

\begin{proof}
Let $q'=q\cdot w$. Take an arbitrary word $u\in A^*$; we have to show that $q\cdot uv=q'\cdot uv$ for a suitable word $v\in A^*$. Clearly,
we may assume that $q\cdot u\ne q'\cdot u$. Since the set $P\cdot wu$ is incompressible, the vertex $q'\cdot u=q\cdot wu$ forms an
incompressible pair with every vertex in $P'\cdot u=P'\cdot wu$. Similarly, since the set $P\cdot u$ is incompressible, the vertex $q\cdot
u$ also forms an incompressible pair with every vertex in $P'\cdot u$, and of course every pair of distinct vertices in $P'\cdot u$ is
incompressible too. Now $P'\cdot u\cup\{q\cdot u,q'\cdot u\}$ has more than $|P|$ elements so it must be compressible, and the above
analysis shows that the only pair in $P'\cdot u\cup\{q\cdot u,q'\cdot u\}$ which may be compressible is the pair $(q\cdot u,q'\cdot u)$,
see Fig.\,\ref{fig:lemma on cliques}.
%\begin{figure}[h]
%\begin{center}
%\unitlength=1.5mm
%\begin{picture}(60,30)
%\gasset{AHnb=0,linewidth=.2} \drawcurve(15,17)(13,29)(25,29)
%\drawcurve(45,17)(47,29)(35,29) \drawcircle(30,15,30)
%\put(14,26){$q\cdot u$} \put(20,12){{\boldmath$P'\cdot u=P'\cdot
%wu$}} \put(14,20){{\boldmath$P\cdot u$}}
%\put(37,20){{\boldmath$P\cdot wu$}}\put(41,26){$q'\cdot u$}
%\end{picture}
%\caption{Configuration in the proof of Lemma~\ref{lemma:maximal
%incompressible}}\label{fig:lemma on cliques}.
%\end{center}
%\end{figure}
Thus, there is a word $v\in A^*$ such that  $q\cdot uv=q'\cdot uv$.
\end{proof}

Suppose that $\mathcal{A}=(Q,A)$ is a complete automaton. Fix a letter $a\in A$ and remove all edges of $\mathcal{A}$ except those labeled
$a$. The remaining graph is called the \emph{underlying graph of $a$}\index{graph!of a letter} or simply the $a$-\emph{graph}. Thus, in the
$a$-graph every vertex is the tail of exactly one edge. From every vertex $q\in Q$, one can start a path in the $a$-graph:
$$q\xrightarrow{a} q\cdot
a\xrightarrow{a}q\cdot a^2\dots\xrightarrow{a} q\cdot a^k\dotsc.$$ Since the set $Q$ is finite, vertices in this path eventually begin
repeating, that is, for some non-negative integer $\ell$ and some integer $m>\ell$ we have $q\cdot a^\ell=q\cdot a^m$.
\begin{figure}[h]
\begin{center}
\unitlength=2mm
\begin{picture}(90,15)(13,0)
\multiput(15,9)(10,0){3}{\circle*{1}} \multiput(16,9)(10,0){2}{\vector(1,0){8}} \multiput(20,10)(10,0){2}{$a$}
\multiput(38,9)(2,0){3}{\circle*{0.2}} \multiput(45,9)(10,0){2}{\circle*{1}} \put(46,9){\vector(1,0){8}} \put(50,10){$a$}
\put(67,11.5){$a$} \put(56,9.5){\vector(2,1){6.4}} \multiput(63,13)(10,0){2}{\circle*{1}} \put(64,13){\vector(1,0){8}} \put(59,9.5){$a$}
\put(74,12.5){\vector(2,-1){6.4}} \put(76,9.5){$a$} \put(82,9){\circle*{1}} \put(81,8.5){\vector(-2,-1){6.4}} \put(77,7.5){$a$}
\multiput(63.3,5)(10,0){2}{\circle*{1}} \multiput(66,5)(2,0){3}{\circle*{0.2}} \put(62.5,5.5){\vector(-2,1){6.4}} \put(60,7.5){$a$} \small
\put(14.3,6){$q$} \put(23.6,6){$q\cdot a$} \put(33.6,6){$q\cdot a^2$} \put(43.4,6){$q\cdot a^{\ell-1}$} \put(53.5,6){$q\cdot a^{\ell}$}
\put(61.3,2){$q\cdot a^{m-1}$} \put(61.3,14.5){$q\cdot a^{\ell+1}$} \put(71.4,14.5){$q\cdot a^{\ell+2}$} \put(80.4,6){$q\cdot a^{\ell+3}$}
\put(71.4,2){$q\cdot a^{\ell+4}$}
\end{picture}
\caption{The orbit of a vertex in the underlying graph of a letter}\label{fig:a-orbit}
\end{center}
\end{figure}
In other words, each path in the $a$-graph eventually arrives at a cycle, see Fig.\,\ref{fig:a-orbit}. The least non-negative integer
$\ell$ such that $q\cdot a^\ell=q\cdot a^m$ for some $m>\ell$ is called the $a$-\emph{height} of the vertex $q$ and the vertex $q\cdot
a^{\ell}$ is called the \emph{bud} of $q$. The cycles of the $a$-graph are referred to as $a$-\emph{cycles}.

\begin{lemma}
\label{lemma:common root} Let $\mathcal{A}=(Q,A)$ be a complete \scn\ automaton. Suppose that there is a letter $a\in A$ such that all
vertices of maximal $a$-height $L>0$ have the same bud. Then $\mathcal{A}$ has a confluent pair.
\end{lemma}


\begin{proof} Let $M$ be the set of all vertices
of $a$-height $L$. Then $q\cdot a^L=q'\cdot a^L$ for all $q,q'\in M$ whence no pair of vertices from $M$ is incompressible. Thus, any
incompressible set in $\mathcal{A}$ has at most one common vertex with $M$. Take  an incompressible set $S$ of maximum size in
$\mathcal{A}$ and choose any vertex $p\in S$. Since the automaton is $\mathcal{A}$ \scn, there is a path from $p$ to a vertex in $M$. If
$u\in A^*$ is the word that labels this path, then $S'=S\cdot u$ is an incompressible set of maximum size and it has exactly one common
vertex with $M$ (namely, $p\cdot u$). Then $S''=S'.a^{L-1}$ is an incompressible set of maximum size that has all its vertices except one
(namely, $p\cdot ua^{L-1}$) in some $a$-cycles---the latter conclusion is ensured by our choice of $L$. If $m$ is the l.c.m. of the lengths
of all simple $a$-cycles, then $r\cdot a^m=r$ for every $r$ in every $a$-cycle but $(p\cdot ua^{L-1})\cdot a=p\cdot ua^{L}\ne p\cdot
ua^{L-1}$. We see that Lemma~\ref{lemma:maximal incompressible} applies (with $S''$ in the role $P$ and $a^m$ in the role of $w$).
\end{proof}

Now we are ready to start the proof of Trahtman's Road Coloring theorem. Let us first explicitly formulate the result.
\begin{theorem}
\label{thm:road coloring} Every \scn\ primitive graph $\Gamma$ with constant out-degree admits a synchronizing coloring.
\end{theorem}

\begin{proof}
If $\Gamma$ has just one vertex, it is nothing to prove. Thus, we assume that $\Gamma$ has more than one vertex and prove that it admits a
coloring with a confluent pair of vertices --- the result will then follow from Proposition~\ref{prop:ckk}.

Fix an arbitrary coloring of $\Gamma$ by letters from an alphabet $A$ and take an arbitrary letter $a\in A$. We induct on the number $N$ of
vertices that do not lie on any $a$-cycle in the chosen coloring i.e. the sum of $a$-height of all vertices in the automaton.

We say that a vertex $p$ of $\Gamma$ is \emph{ramified}\index{vertex!ramified} if it serves as the tail for some edges with different
heads.

Suppose first that $N=0$. This means that all vertices belong to $a$-cycles (i.e. the $a$-height of every vertex is 0). If we suppose that
no vertex in $\Gamma$ is ramified, then there is just one $a$-cycle (since $\Gamma$ is \scn) and all cycles in $\Gamma$ have the same
length. This contradicts the assumption that $\Gamma$ is primitive\footnote{This is the only place in the whole proof where primitivity is
used!}.

Thus, let $p$ be a vertex which is ramified. Then there exists a letter $b\in A$ such that the vertices $q = p\cdot a$ and  $r = p\cdot b$
are not equal. We exchange the labels of the edges $p\stackrel{a}{\to}q$ and $p\stackrel{b}{\to}r$, see Fig.\,\ref{fig:rcp-basis}.
%\begin{figure}[h]
%\begin{center}
%\unitlength .8mm
%\begin{picture}(200,40)(13.5,-15)
%\node(A)(20,-5){} \node(B)(30,15){} \node(C)(55,22){$p$}
%\node(D)(80,15){$q$} \node(E)(90,-5){} \node(X)(65,5){$r$}
%\drawedge(A,B){$a$} \drawedge(B,C){$a$} \drawedge(D,E){$a$}
%\drawedge[dash={1.5}0,ELside=r,curvedepth=5](E,A){$a^k$}
%\drawedge(C,D){$a$} \drawedge[linewidth=.6](C,X){$b$}
%\node(A1)(120,-5){} \node(B1)(130,15){} \node(C1)(155,22){$p$}
%\node(D1)(180,15){$q$} \node(E1)(190,-5){} \node(X1)(165,5){$r$}
%\drawedge[linewidth=.6](C1,D1){$b$} \drawedge(C1,X1){$a$}
%\drawedge(A1,B1){$a$} \drawedge(B1,C1){$a$} \drawedge(D1,E1){$a$}
%\drawedge[dash={1.5}0,ELside=r,curvedepth=5](E1,A1){$a^k$}
%\end{picture}
%\end{center}
%\caption{Recoloring in the induction basis}\label{fig:rcp-basis}
%\end{figure}
It is clear that in the new coloring there is only one vertex of maximal $a$-height, namely, the vertex $q$. Thus, Lemma~\ref{lemma:common
root} applies and the induction basis is verified.

Now suppose that $N>0$. We denote by $L$ the maximum $a$-height of the vertices in the chosen coloring. Observe that $N>0$ implies $L>0$.

Let $p$ be a vertex of height $L$. Since $\Gamma$ is strongly connected, there is an edge $p'\to p$ with $p'\ne p$, and by the choice of
$p$, the label of this edge is some letter $b\ne a$. Let $t=p'\cdot a$. One has $t\ne p$. Let $r = p\cdot a^L$ be the bud of $p$ and let
$C$ be the $a$-cycle on which $r$ lies.

The following considerations split in several cases. In each case except one we can recolor $\Gamma$ by swapping the labels of two edges so
that the new coloring either satisfies the premise of Lemma~\ref{lemma:common root} (all vertices of maximal $a$-height have the same bud)
or has more vertices on the $a$-cycles (and the induction assumption applies). In the remaining case finding a confluent pair will be easy.

\medskip

 \textbf{Case 1: $p'$ is not on $C$.}

%\begin{figure}[h]
%\begin{center}
%\unitlength .9mm
%\begin{picture}(130,24)
%\node(A)(0,10){$p'$} \node(B)(15,20){$p$} \node(C)(15,0){$t$}
%\node(D)(40,20){$r$} \drawedge[dash={1.5}0](B,D){$a^L$}
%\drawloop[dash={1.5}0,loopangle=0](D){$a^k$}
%\drawedge[linewidth=.6](A,B){$b$} \drawedge(A,C){$a$}
%\node(A1)(80,10){$p'$} \node(B1)(95,20){$p$} \node(C1)(95,0){$t$}
%\node(D1)(120,20){$r$} \drawedge[dash={1.5}0](B1,D1){$a^L$}
%\drawloop[dash={1.5}0,loopangle=0](D1){$a^k$}
%\drawedge(A1,B1){$a$} \drawedge[linewidth=.6](A1,C1){$b$}
%\end{picture}
%\end{center}
%\caption{Recoloring in Case 1}\label{fig:rcp-case1}
%\end{figure}

We swap the labels of $p'\stackrel{b}{\to}p$ and $p'\stackrel{a}{\to}t$, see Fig.\,\ref{fig:rcp-case1}. If $p'$ was on the $a$-path from
$p$ to $r$, then the swapping creates a new $a$-cycle increasing the number of vertices on the $a$-cycles. If $p'$ was not on the $a$-path
from $p$ to $r$, then the $a$-height of $p'$ becomes $L+1$ whence all vertices of maximal $a$-height in the new automaton are
$a$-ascendants of $p'$ and thus have $r$ as the common bud.

\medskip

\textbf{Case 2: $p'$ is on $C$.} Let $k_1$ be the least integer such that $r\cdot a^{k_1}=p'$. The vertex $t=p'\cdot a$ is also on $C$. Let
$k_2$ be the least integer such that $t\cdot a^{k_2}=r$. Then the length of $C$ is $k_1+k_2+1$.

%\begin{figure}[h]
%\begin{center}
%\unitlength .9mm
%\begin{picture}(130,24)
%\node(A)(0,15){$p'$} \node(B)(15,15){$p$} \node(C)(15,0){$t$}
%\node(D)(40,15){$r$} \drawedge[dash={1.5}0](B,D){$a^L$}
%\drawedge[dash={1.5}0,curvedepth=-8,ELside=r](D,A){$a^{k_1}$}
%\drawedge[dash={1.5}0,curvedepth=-3,ELside=r](C,D){$a^{k_2}$}
%\drawedge[linewidth=.6](A,B){$b$} \drawedge(A,C){$a$}
%\node(A1)(80,15){$p'$} \node(B1)(95,15){$p$} \node(C1)(95,0){$t$}
%\node(D1)(120,15){$r$} \drawedge[dash={1.5}0](B1,D1){$a^L$}
%\drawedge[dash={1.5}0,curvedepth=-8,ELside=r](D1,A1){$a^{k_1}$}
%\drawedge[dash={1.5}0,curvedepth=-3,ELside=r](C1,D1){$a^{k_2}$}
%\drawedge(A1,B1){$a$} \drawedge[linewidth=.6](A1,C1){$b$}
%\end{picture}
%\end{center}
%\caption{Recoloring in Subcase 2.1}\label{fig:rcp-subcase21}
%\end{figure}

\textbf{Subcase 2.1: $k_2\ne L$.} Again, we swap the labels of $p'\stackrel{b}{\to}p$ and $p'\stackrel{a}{\to}t$, see
Fig.\,\ref{fig:rcp-subcase21}. If $k_2<L$, then the swapping creates an $a$-cycle of length $k_1+L+1>k_1+k_2+1$ increasing the number of
vertices on the $a$-cycles. If $k_2>L$, then the $a$-height of $t$ becomes $k_2$ whence all vertices of maximal $a$-height in the new
automaton are $a$-ascendants of $t$ and thus have the same bud.

\medskip

Let $s$ be the vertex of $C$ such that $s\cdot a=r$.

\textbf{Subcase 2.2: $k_2=L$ and $s$ is ramified.} Since $s$ is ramified, there is a letter $c$ such that $s'=s\cdot c\ne r$.

%\begin{figure}[h]
%\begin{center}
%\unitlength .9mm
%\begin{picture}(135,26)(0,-2)
%\node(A)(0,15){$p'$} \node(B)(15,15){$p$} \node(C)(0,0){$t$}
%\node(D)(40,15){$r$} \node(E)(30,0){$s$} \node(F)(45,0){$s'$}
%\drawedge[dash={1.5}0](B,D){$a^L$}
%\drawedge[dash={1.5}0,curvedepth=-8,ELside=r](D,A){$a^{k_1}$}
%\drawedge[dash={1.5}0,ELside=r](C,E){$a^{k_2-1}$}
%\drawedge(E,D){$a$} \drawedge[linewidth=.6](E,F){$c$}
%\drawedge(A,B){$b$} \drawedge(A,C){$a$} \node(A1)(85,15){$p'$}
%\node(B1)(100,15){$p$} \node(C1)(85,0){$t$} \node(D1)(125,15){$r$}
%\node(E1)(115,0){$s$} \node(F1)(130,0){$s'$}
%\drawedge[dash={1.5}0](B1,D1){$a^L$}
%\drawedge[dash={1.5}0,curvedepth=-8,ELside=r](D1,A1){$a^{k_1}$}
%\drawedge[dash={1.5}0,ELside=r](C1,E1){$a^{k_2-1}$}
%\drawedge[linewidth=.6](E1,D1){$c$} \drawedge(E1,F1){$a$}
%\drawedge(A1,B1){$b$} \drawedge(A1,C1){$a$}
%\end{picture}
%\end{center}
%\caption{Recoloring in Subcase 2.2}\label{fig:rcp-subcase22}
%\end{figure}

We swap the labels of $s\stackrel{c}{\to}s'$ and $s\stackrel{a}{\to}r$, see Fig.\,\ref{fig:rcp-subcase21}. If $r$ still lies on an
$a$-cycle, then the length of the $a$-cycle is at least $k_1+k_2+2$ and the number of vertices on the $a$-cycles increases. Otherwise, the
$a$-height of $r$  becomes at least $k_1+k_2+1>L$ whence all vertices of maximal $a$-height in the new automaton are $a$-ascendants of $r$
and have a common bud.

\medskip

Let $q$ be the vertex on the $a$-path from $p$ to $r$ such that $q\cdot a=r$.

\textbf{Subcase 2.3: $k_2=L$ and $q$ is ramified.} Since $q$ is ramified, there is a letter $c$ such that $q'=q\cdot c\ne r$.

%\begin{figure}[h]
%\begin{center}
%\unitlength .9mm
%\begin{picture}(135,28)(0,-2)
%\node(A)(0,15){$p'$} \node(B)(15,15){$p$} \node(C)(0,0){$t$}
%\node(D)(50,15){$r$} \node(E)(35,15){$q$} \node(F)(25,5){$q'$}
%\drawedge[dash={1.5}0](B,E){$a^{L-1}$}
%\drawedge[dash={1.5}0,curvedepth=-8,ELside=r](D,A){$a^{k_1}$}
%\drawedge[dash={1.5}0,ELside=r,ELpos=70,curvedepth=-10](C,D){$a^{k_2}$}
%\drawedge(E,D){$a$} \drawedge(E,F){$c$}
%\drawedge[linewidth=.6](A,B){$b$} \drawedge(A,C){$a$}
%\node(A1)(85,15){$p'$} \node(B1)(100,15){$p$} \node(C1)(85,0){$t$}
%\node(D1)(135,15){$r$} \node(E1)(120,15){$q$}
%\node(F1)(110,5){$q'$} \drawedge[dash={1.5}0](B1,E1){$a^{L-1}$}
%\drawedge[dash={1.5}0,curvedepth=-8,ELside=r](D1,A1){$a^{k_1}$}
%\drawedge[dash={1.5}0,ELside=r,ELpos=70,curvedepth=-10](C1,D1){$a^{k_2}$}
%\drawedge(E1,D1){$a$} \drawedge(E1,F1){$c$} \drawedge(A1,B1){$a$}
%\drawedge[linewidth=.6](A1,C1){$b$}
%\end{picture}
%\end{center}
%\caption{Recoloring reducing Subcase 2.3 to Subcase
%2.2}\label{fig:rcp-subcase23}
%\end{figure}

If we swap the labels of $p'\stackrel{b}{\to}p$ and $p'\stackrel{a}{\to}t$, then we find ourselves in the conditions of Subcase~2.2 (with
$q$ and $q'$ playing the roles of $s$ and $s'$ respectively), see Fig.\,\ref{fig:rcp-subcase23}.

\medskip

\textbf{Subcase 2.4: $k_2=L$ and neither $s$ nor $q$ is ramified.}

%\begin{figure}[h]
%\begin{center}
%\unitlength .9mm
%\begin{picture}(90,30)(0,-7.5)
%\node(A)(0,15){$p'$} \node(B)(15,15){$p$} \node(C)(0,-5){$t$}
%\node(D)(50,5){$r$} \node(E)(35,15){$q$} \node(F)(35,-5){$s$}
%\drawedge[dash={1.5}0](B,E){$a^{L-1}$}
%\drawedge[dash={1.5}0,curvedepth=5,ELside=r](D,A){$a^{k_1}$}
%\drawedge[dash={1.5}0](C,F){$a^{k_2-1}$} \drawedge(E,D){}
%\drawedge[curvedepth=3](E,D){$a$} \drawedge[curvedepth=-3](E,D){}
%\drawedge(A,B){$b$} \drawedge(A,C){$a$} \drawedge(F,D){}
%\drawedge[curvedepth=3](F,D){}
%\drawedge[curvedepth=-3,ELside=r](F,D){$a$}
%\end{picture}
%\end{center}
%\caption{Subcase 2.4}\label{fig:rcp-subcase24}
%\end{figure}

In this subcase it is clear that $q$ and $s$ form a confluent pair whichever coloring of $\Gamma$ is chosen,
see~Fig.\,\ref{fig:rcp-subcase24}. This completes the proof.
\end{proof}

The above proof of Theorem~\ref{thm:road coloring} is constructive and can be ``unfolded'' to a relatively fast algorithm that, given a
\scn\ primitive graph $\Gamma$ with constant out-degree, finds a synchronizing coloring of $\Gamma$, see~\cite{Beal&Perrin:2008}.

If one drops the primitivity condition, one can prove (basically by the same method) the following generalization of the Road Coloring
Theorem, see~\cite{Beal&Perrin:2008}:

\begin{theorem}
\label{thm:rcp-imprimitive} Suppose that $d$ is the g.c.d. of the lengths of cycles in a \scn\ graph $\Gamma=(V,E)$ with constant
out-degree.  Then $\Gamma$ admits a coloring for which there is a word $w$ such that $|V\cdot w|=d$.
\end{theorem}

Finally, we discuss a general version of the Road Coloring Problem in which graphs are not assumed to be \scn. Given an arbitrary graph
$\Gamma=(V,E)$, a vertex $q$ is said to be \emph{reachable} from a vertex $p$ if there is a path from $p$ to $q$. Clearly,  the
\emph{reachability relation}\index{reachability relation} is reflexive (recall that a path may be empty) and transitive, and the mutual
reachability relation is an equivalence on the set $V$. The subgraphs induced on the classes of the mutual reachability relation are \scn\
and are called the \emph{\scn\ components} of the graph $\Gamma$.\index{strongly connected component} The reachability relation induces a
partial order on the set of the \scn\ components: a component $\Gamma_1$ precedes a component $\Gamma_2$ in this order if some vertex of
$\Gamma_1$ is reachable from some vertex of $\Gamma_2$. The following result shows that the general case of the Road Coloring Problem
easily reduces to its \scn\ case (solved by Theorem~\ref{thm:road coloring}):

\begin{cor}
\label{cor:rcp-general} A graph $\Gamma$ with constant out-degree admits a synchronizing coloring if and only if $\Gamma$ has the least
\scn\ component and this component is primitive.
\end{cor}

\begin{ex}
Prove Corollary~\ref{cor:rcp-general}.
\end{ex}

An interesting issue related to the Road Coloring Problem is the choice of the \emph{optimal} synchronizing coloring for a given graph.
Clearly, graphs admitting a synchronizing coloring may have many synchronizing colorings and the minimum length of \sws\ for the resulting
\sa\ may drastically differ. For instance, it is easy to see that the \v{C}ern\'y automaton $\mathcal{C}_n$ that cannot be reset by any
word of length less than $(n-1)^2$ (see Proposition~\ref{prop:cerny} admits a recoloring with a \sw\ of length as low as $n-1$ (and
moreover, every \scn\ graph $\Gamma$ with constant out-degree that has a loop admits a synchronizing coloring for which the minimum length
of \sws\ is less than the number of vertices of $\Gamma$). Nevertheless, there exist graphs whose synchronizing coloring are ``slowly''
\sa. As an example, consider the \emph{Wielandt graph}\index{graph!Wielandt} $W_n$ shown in Figure~\ref{fig:Wielandt}.
%\begin{figure}[ht]
%\begin{center}
%\unitlength .45mm
%\begin{picture}(72,72)(0,-72)
%\gasset{Nw=16,Nh=16,Nmr=8} \node(n0)(36.0,-16.0){1} \node(n1)(4.0,-40.0){$0$}
%\node(n2)(68.0,-40.0){2} \node(n3)(16.0,-72.0){$n{-}1$}
%\node(n4)(56.0,-72.0){3} \drawedge(n1,n0){} \drawedge[curvedepth=2](n2,n4){}
%\drawedge[curvedepth=-2](n2,n4){} \drawedge[curvedepth=2](n0,n2){}
%\drawedge[curvedepth=-2](n0,n2){} \drawedge[curvedepth=2](n3,n1){}
%\drawedge[curvedepth=-2](n3,n1){} \drawedge(n1,n2){} \put(32,-73){$\dots$}
%\end{picture}
%\end{center}
%\caption{The graph $W_n$}\label{fig:Wielandt}
%\end{figure}
It has $n$ vertices $0,1,\dots,n-1$, say, and $2n$ edges: two edges from $i$ to $i+1\pmod n$ for each $i=1,\dots,n-1$, and the edges from
$0$ to $1$ and $2$. The graph (more precisely, its incidence matrix) first appeared in Wielandt's seminal paper~\cite{Wielandt:1950} where
Wielandt stated that for every primitive non-negative $n\times n$-matrix $M$, the matrix $M^{(n-1)^2+1}$ is positive. The incidence matrix
of $W_n$ was used to show that this bound is tight (that is, its $(n-1)^2$-th power still has some 0 entries); later it was observed to be
the only (up to a simultaneous permutation of rows and columns) matrix with this property, see~\cite{Dulmage&Mendelson:1964}.

It is easy to realize that every coloring of the graph $W_n$ is isomorphic to the automaton $\mathcal{W}_n$ shown in
Figure~\ref{fig:cerny-n} on the right. Since $W_n$ is \scn\ and primitive, the Road Coloring Theorem implies that $\mathcal{W}_n$ is
synchronizing (of course, this can also be verified directly). In \cite{Ananichev&Gusev&Volkov:2010} it is shown that the minimum length of
\sws\ for $\mathcal{W}_n$ is $n^2-3n+3$, see the proof of Proposition~\ref{prop:cerny} above. The aforementioned extremal property of the
Wielandt graphs gives some evidence for conjecturing that this series of graphs may yield the extremal value also for the minimum length of
\sws\ for synchronizing colorings of $n$-vertex graph. In other words, we suggest a conjecture that is in a sense parallel to the
\v{C}ern\'{y} one.
\begin{conjecture}
\label{conj:hybrid} Every \scn\ primitive graph with constant out-degree and $n$ vertices admits a synchronizing coloring that can be reset
by a word of length $n^2-3n+3$.
\end{conjecture}
We observe that while there is a clear analogy between Conjecture~\ref{conj:hybrid} and the \v{C}ern\'{y} conjecture, the validity of none
of them immediately implies the validity of the other.

Some partial results related to Conjecture~\ref{conj:hybrid} can be found in~\cite{Steinberg:2010archive,Carpi&D'Alessandro:2010}.


\section{Applications of the Road Coloring Theorem}

\subsection{Application to symbolic dynamics}

A major open problem of symbolic dynamics is the so-called \emph{conjugacy problem}\index{conjugacy problem} for subshifts of finite type:
to find a necessary and sufficient condition for the two subshifts of finite type to be isomorphic. Here an isomorphism (symbolic dynamists
prefer to use the term ``conjugacy'') between two subshifts $S_1$ and $S_2$ is a continuous bijection $f:S_1\to S_2$ that commutes with the
shift operation (i.e.\ $f(T(\alpha))=T(f(\alpha))$ for each $\alpha\in S_1$).\index{conjugacy (of subshifts)} Several \emph{conjugacy
invariants}\index{conjugacy invariant} are known but no complete set of invariants which would characterize subshifts of finite type up to
conjugacy is known so far. One of the main invariants of a subshift is its entropy\index{subshift!entropy of} $h(S)$ defined as
\begin{equation}
\label{eq:entropy} h(S)=\lim_{n\to\infty}\frac1n\log s_n
\end{equation}
where $s_n$ stands for the number of different subwords of length $n$ in words of $S$.





\begin{ex}
Prove that the limit in \eqref{eq:entropy} exists for every subshift $S$.
\end{ex}




\begin{ex}
Calculate the entropy of

\begin{itemize}
\item the full shift on a $k$-letter alphabet,
\item  the golden mean subshift.
\end{itemize}
\end{ex}

\begin{ex}
Prove that the entropy of a subshift is a conjugacy invariant.
\end{ex}

In general if $X$ is a compact topological space and $T$ is a homeomorphism $X\to X$, then the entropy of the dynamical system $(X,T)$ is
defined as follows. For every open cover ${\mathcal U}$ of $X$ let $N({\mathcal U})$ is the number of elements of ${\mathcal U}$ still
covering $X$. If ${\mathcal U,V}$ are two open covers of $X$, then $\mathcal{U}\wedge \mathcal{V}$ is the cover of $X$ consisting of all
intersection of $U\in \mathcal{U}$ and $V\in \mathcal{V}$. Now if $\mathcal{U}$ is a finite open cover of $X$, let $h(\mathcal{U})$ be the
limit
$$\lim_{n\to\infty} \frac{\log_2 N(\mathcal{U}\wedge
T\iv\mathcal{U}\wedge\ldots\wedge T^{-n}\mathcal{U})}{n}$$  where $T^k(\mathcal{U})$ is the image of $\mathcal U$ under $T^k$ (the limit
always exists). Then the \emph{entropy}\index{entropy of a dynamical system} $h$ of $(X,T)$ is the infimum of $h(\mathcal U)$ for all
$\mathcal U$.


\begin{ex}\label{ex:entropy} Show that in the case of a subshift, the two definitions of entropy given above coincide.
\end{ex}


Since no classification of subshifts of finite type up to conjugacy is known, more ``rough'' approaches in which subshifts of finite type
are classified up to some less rigid relationship are of interest. The Road Coloring theorem easily leads to a neat result in this
direction. In Section~\ref{sec:symbolic dynamics} we have seen that every coloring of a graph $\Gamma$ induces a natural 1-block map $f$
from the edge subshift $S_{\Gamma}$ onto the sofic subshift recognized by the coloring: $f$ sends each bi-infinite path in $S_{\Gamma}$ to
its label sequence. If the coloring happens to deterministic, the map $f$ is right-resolving. (A map $g$ between two subshifts
$S_1\subseteq\az$ and $S_2\subseteq B^\Z$  is said to be \emph{right-resolving}\index{morphism (of subshifts)!right-resolving} if there is
an integer $k>1$ such that for $\beta=g(\alpha)$, the $k$-block $\alpha(-k,-1)\in A^k$ and the letter $\beta(0,0)\in B$ uniquely determine
the letter $\alpha(0,0)$.) Indeed, if an edge $e$ of $\Gamma$ occurs in a bi-infinite path $\alpha\in S_{\Gamma}$ and we know the label $a$
(in a fixed deterministic coloring of $\Gamma$) of the next edge in $\alpha$, then we also know this next edge because in a deterministic
automaton only one edge leaving the vertex $h(e)$ can be labeled $a$. Right-resolving maps have many nice properties; in particluar, they
are \emph{finite-to one}\index{morphism (of subshifts)!finite-to-one} (this means that for every $\beta$ in the image of $f$ there are only
finitely many $\alpha$ with $f(\alpha)=\beta$).
\begin{ex}
Prove that every right-resolving map is finite-to-one.
\end{ex}

If $\Gamma$ has constant out-degree $k$, one can take an alphabet $A$ with $k$ letters and color $\Gamma$ such that the resulting automaton
$\mathcal{A}$ will be complete. Such a coloring induces a right-resolving map $f$ from $S_{\Gamma}$ onto the full shift \az. Now suppose
that the coloring happens to be synchronizing. Let $w$ be a \sw\ for the automaton $\mathcal{A}$ and let $\ell=|w|$. Consider the set
$\overleftarrow{W}$ of all bi-infinite words $\beta$ such that for every $n\in\Z$ there is an $m$ with $m+\ell\le n$ and
$\beta(m,m+\ell-1)=w$; this means that $w$ occurs as a subword in $\beta$ to the left of any given position. Clearly, $\overleftarrow{W}$
is shift invariant, and it is easy to see that for every $\beta\in\overleftarrow{W}$ there is a unique $\alpha$ such that
$f(\alpha)=\beta$. Indeed, to recover the edge $\alpha(n,n)$, look at some occurrence of $w$ as $w=\beta(m,m+\ell-1)$ with $m+\ell\le n$.
Since $w$ is a \sw, every path in $\Gamma$ labeled $w$ ends at the same vertex $q$, and in a deterministic automaton there is exactly one
path starting at $q$ and labeled $\beta(m+\ell,n)$. The edge $\alpha(n,n)$ is the last one in this unique path, and therefore, is uniquely
determined.

We see that the map $f$ is invertible on $\overleftarrow{W}$, so we have a one-to-one correspondence between $f^{-1}(\overleftarrow{W})$
and $\overleftarrow{W}$. Observe that the sets $f^{-1}(\overleftarrow{W})$ and $\overleftarrow{W}$ are ``big'', namely, their complements
in respectively $S_{\Gamma}$ and \az\ can be easily shown to have measure 0 with respect to every shift invariant ergodic probability
measure on \az\ which is positive on open sets\footnote{A concrete example of such measure is the \emph{Bernoulli measure} defined by
assigning to each letter $a\in A$ a \emph{probability} $p_a$ (a real number with $0<p_a<1$) such that $\sum_{a\in A}p_a=1$. Now the measure
of \emph{cylinder sets} $C(w)=\{\alpha\in\az\mid \alpha(0,\ell-1)=a_1a_2\cdots a_\ell\}$ is set to be equal to $p(w)=p_{a_1}p_{a_2}\cdots
p_{a_\ell}$.}. (A probability measure on \az\ is said to be \emph{ergodic} if every Borel set $X$ such that $T^{-1}(X)=X$ has measure 0 or
1.)\index{measure!ergodic}
\begin{ex}
Prove that the complement of $\overleftarrow{W}$ has Bernoulli measure 0.
\end{ex}

By a \emph{relational morphism}\index{morphism (of subshifts)!relational} between two subshifts $S_1$ and $S_2$ we mean a closed subalgebra
of $S_1\times S_2$ whose projections on both components are onto. Examples of relational morphisms include $\{(\alpha,f(\alpha))\mid
\alpha\in S_1\}$ and $\{(f^{-1}(\beta),\beta)\mid \beta\in S_2\}$ where $f:S_1\to S_2$ is an onto morphism. A relational morphism $\rho$
between $S_1$ and $S_2$ is said to be \emph{one-to-one almost everywhere}\index{morphism (of subshifts)!relational!one-to-one almost
everywhere} if there exist shift invariant subsets $N_1\subset S_1$ and $N_2\subset S_2$ of measure 0 (with respect to every shift
invariant ergodic probability measure which is positive on open sets) such that $\rho$ is a one-to-one correspondence between $S_1\setminus
N_1$ and $S_2\setminus N_2$. In this case, the subshifts are up to a ``negligible'' piece isomorphic, in both topological (as compact
spaces) and algebraic (as unary algebras) sense.

If $\rho_1$ is a relational morphism between $S_1$ and $S_2$ and $\rho_2$ is a relational morphism between $S_2$ and $S_3$, then the usual
relational product $\rho_1\circ\rho_2$ is easily seen to be a relational morphism between $S_1$ and $S_3$ which is one-to-one almost
everywhere if so are both $\rho_1$ and $\rho_2$. With this notion in hand, the above arguments yield obtain the following corollary of the
Road Coloring theorem:
\begin{cor}
\label{cor:agw} If $\Gamma_1$ and $\Gamma_2$ are primitive graphs with the same constant out-degree, then there is a relational morphism
between the edge subshifts $S_{\Gamma_1}$ and $S_{\Gamma_2}$ which is one-to-one almost everywhere.
\end{cor}

\begin{proof}
By the Road Coloring theorem there exist synchronizing colorings of $\Gamma_1$ and $\Gamma_2$ by letters of some alphabet $A$. These
colorings give rise to right-resolving surjective maps $f_1:S_{\Gamma_1}\to\az$ and $f_2:S_{\Gamma_2}\to\az$ which are one-to-one almost
everywhere. The product of $f_1$ with $f_2^{-1}$ is the desired relational morphism.
\end{proof}

It was Corollary~\ref{cor:agw} that led Adler, Goodwyn and Weiss to their explicit formulation of the Road Coloring Conjecture
in~\cite{Adler&Goodwyn&Weiss:1977}. In fact, they were able to bypass the conjecture and proved the corollary (in fact, a slightly more
general result) in~\cite{Adler&Goodwyn&Weiss:1977}.

It is easy hard to calculate that the entropy of the edge subshift $S_{\Gamma}$ where $\Gamma$ is a \scn\ graph with constant out-degree
$k$ is equal to $\log k$. Thus, Corollary~\ref{cor:agw} can be stated in terms of entropy as saying that in the class of subshifts of the
form $S_{\Gamma}$ with $\Gamma$ being primitive and of constant out-degree, each subshift is characterized by its entropy up to a
relational morphism which is one-to-one almost everywhere. The reader who is interested in further developments in this area is referred
to~\cite{Adler&Marcus:1979} and also to the book~\cite{Lind&Marcus:1995}.

\subsection{Application to coding theory}

Another interesting application of the Road Coloring theorem comes from the coding theory, more precisely, from the theory of
variable-length codes. Suppose we deal with data presented as a huge word $w$ in some finite source alphabet $B$, and we know---or can
estimate---the probability of occurrence in $w$ for each letter from $A$.\footnote{A good example is a long text in a natural language,
like Marcel Proust's ``\`A la recherche du temps perdu'' with its approx.\ 9,609,000 characters, each letter and space being counted as one
character. We can quite accurately estimate the probability of occurrence in this text for each character using available information about
relative frequencies of letters in the French language. For instance, `e' occurs in French words approx.\ twice as often as `a' and the
frequency of occurrence of `k' is less than 0.9\% of that of `l'.} If we want to digitalize the data (for storing or transmitting them), we
have to encode the letters of $B$ with some words over a smaller alphabet $A$, usually, the binary alphabet $\{0,1\}$. An encoding of
letters by binary words of constant length (such as ANSII-codes) requires $\lceil\log_2|B|\rceil$ bits for each letter and thus
$|w|\cdot\lceil\log_2|B|\rceil$ bits for the whole word $w$. However, by a clever variable-length encoding we may save much space (in the
case of data storage) and/or time (in the case of data transmission). For this, we should encode letters that occur in $w$ more frequently
by shorter binary words while letters with low probability of occurrence in $w$ may be encoded by longer binary words without much harm.
This simple idea was already used in Morse code of the 19th century: `e', the most common letter in English has the shortest Morse code, a
single dot.

A complication has to be taken into account when variable-length encoding is used: the process of decoding, i.e. restoring the original
word $w$ from a stream of bits in that $w$ has been encoded, may be not easy in general. There is however a class of encodings for which
this complication does not appear. A \emph{prefix code}\index{prefix code} is a set $X$ of words over some alphabet such that no word of
$X$ is a prefix of another word of $X$. Data encoded with a prefix code can be decoded on-the-fly: a decoder just keeps finding and
removing prefixes that form valid code words from the incoming stream. At the same time, it is known that the most economical binary
presentation of data that can be achieved by any variable-length encoding always can be achieved by a suitable encoding with a prefix code.


\begin{example}
\label{examp:you use a code c} Consider the following set of binary words:
$$C=\{000,0010,0011,010,0110,0111,10,110,111\}.$$
Clearly, it is a prefix code. We can use this code to efficiently encode the sentence YOU USE A CODE C. This sentence involves 9 different
characters (8 letters and space) and has length 16 so that every its constant-length binary encoding requires $16\cdot\lceil\log_2
9\rceil=64$ bits. Since space occurs 4 times, each of C,E,O,U occurs twice, and each of A,D,S,Y occurs once, it suggests the following
encoding.
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline space & C   & E   & O   & U   &  A   & D    & S    &  Y\\
\hline 10    & 000 & 010 & 110 & 111 & 0010 & 0011 & 0110 & 0111\\
\hline
\end{tabular}
\end{center}
The sentence YOU USE A CODE C is then encoded with the binary word
$$0111\mid110\mid111\mid10\mid111\mid0110\mid010\mid10\mid0010\mid10\mid000\mid110\mid0011\mid010\mid10\mid000$$
of length 48 (vertical lines separating code words are inserted for readability only). We have thus reduced the binary representation size
by 25\%.
\end{example}

\begin{ex}
Show that the encoding suggested in Example~\ref{examp:you use a code c} is optimal: no other encoding of the 9 characters \{space, C, E,
O, U, A, D, S, Y\} by binary words can produce a shorter binary word for the sentence YOU USE A CODE C that could be uniquely decoded.
\end{ex}

A prefix code is \emph{maximal}\index{prefix code!maximal} if it is not contained in another prefix code over the same alphabet. A maximal
prefix code $X$ over $A$ is \emph{synchronized}\index{prefix code!synchronized} if there is a word $x\in X^*$ such that for any word $w\in
A^*$, one has $wx\in X^*$. Such a word $x$ is called a \emph{synchronizing word}\index{synchronizing word of a code} for $X$. The advantage
of synchronized codes is that they are able to recover after a loss of synchronization between the decoder and the coder caused by channel
errors: in the case of such a loss, it suffices to transmit a synchronizing word and the following symbols will be decoded correctly.
Moreover, since the probability that a word $v\in A^*$ contains a fixed factor $x$ tends to 1 as the length of $v$ increases, synchronized
codes eventually resynchronize by themselves, after sufficiently many symbols being sent. (As shown
in~\cite{Capocelli&Gargano&Vaccaro:1988}, the latter property in fact characterizes synchronized codes.) The binary code
$C=\{000,0010,0011,010,0110,0111,10,110,111\}$ used in Example~\ref{examp:you use a code c} can illustrate this notion. Indeed, $C$ is a
maximal prefix code and one can easily check that each of the words 010, 011110, 011111110, \dots\ is a synchronizing word for $C$. For
instance, if the code word 000 has been sent but, due to a channel error, the word 100 has been received, the decoder interprets 10 as a
code word, and thus, loses synchronization. However, with a high probability this synchronization loss only propagates for a short while;
in particular, the decoder definitely resynchronizes as soon as it encounters one of the segments 010, 011110, 011111110, \dots\ in the
received stream of symbols. A few samples of such streams are shown in Figure~\ref{fig:decoding} in which vertical lines show the partition
of each stream into code words and the boldfaced code words indicate the position at which the decoder resynchronizes.
\begin{figure}[h]
\begin{center}
\begin{tabular}{ll}
Sent & $0\,0\,0\ \mid 0\,0\,1\,0\,\ \mid\mathbf{0\,1\,1\,1\mid\dots}$\\
\mathstrut Received & $1\,0\mid 0\,0\,0 \mid 1\,0 \mid\mathbf{0\,1\,1\,1\mid\dots}$\\
\hline
\mathstrut Sent & $0\,0\,0\mid 0\,1\,1\,1 \mid 1\,1\,0\mid 0\,0\,1\,1 \mid 0\,0\,0 \mid 1\,0 \mid\mathbf{1\,1\,0\mid \dots}$\\
\mathstrut Received & $1\,0\mid 0\,0\,1\,1 \mid 1\,1\,1 \mid 0\,0\,0\mid 1\,1\,0 \mid 0\,0\,1\,0 \mid\mathbf{1\,1\,0\mid \dots}$\\
\hline
\mathstrut Sent & $0\,0\,0\mid 0\,0\,0 \mid 1\,1\,1\mid\mathbf{1\,0\mid \dots}$\\
\mathstrut Received & $1\,0\mid 0\,0\,0 \mid 0\,1\,1\,1 \mid\mathbf{1\,0\mid \dots}$
\end{tabular}
\caption{Restoring synchronization}\label{fig:decoding}
\end{center}
\end{figure}

If $X$ is a finite prefix code over an alphabet $A$, then its decoding can be implemented by a deterministic automaton that is defined as
follows. Let $Q$ be the set of all proper prefixes of the words in $X$ (including the empty word 1). For $q\in Q$ and $a\in A$, define
\begin{displaymath}
q\cdot a =\begin{cases} qa & \text{if $qa$ is a proper prefix of a word of $X$}\,,\\
1 & \text{if $qa \in X$}\,.\end{cases}
\end{displaymath}
The resulting automaton $\mathcal{A}_X$ is complete whenever the code $X$ is maximal and it is easy to see that $\mathcal{A}_X$ is a \san\
if and only if $X$ is a synchronized code. Moreover, a word $x$ is synchronizing for $X$ if and only if $x$ is a \sw\ for $\mathcal{A}_X$
and sends all vertices in $Q$ to the vertex $1$.

The compression capacity of a maximal prefix code $X$ depends only on the lengths of the words in $X$, not on the words themselves. In
contrast, the property of being synchronized does depend on the code words. For instance, the maximal prefix code
$D=\{0000,0001,001,0100,0101,011,100,101,11\}$ has the same distribution of code word lengths as the code
$C=\{000,0010,0011,010,0110,0111,10,110,111\}$ from Example~\ref{examp:you use a code c} but $D$ is not synchronized while $C$ is.
\begin{ex}
Construct the automata $\mathcal{A}_C$ and $\mathcal{A}_D$ and verify that the former is synchronizing while the latter is not. Compare the
underlying graphs of these automata.
\end{ex}

Since the property of being synchronized is a ``positive'' feature of a code, it is rather natural to ask under which conditions, given a
maximal prefix code $X$, one can find a synchronized code with the same distribution of code word lengths. In order to answer this
question, observe that words in $X$ precisely correspond to simple cycles in the automaton $\mathcal{A}_X$. Thus, the Road Coloring theorem
immediately implies
\begin{cor}
\label{cor:schutzenberger} Let $\{w_1,\dots,w_n\}$ be a maximal prefix code and $|w_i|=\ell_i$, $i=1,\dots, n$. A synchronized code
$\{v_1,\dots,v_n\}$ such that $|v_i|=\ell_i$ for all $i=1,\dots,n$ exists if and only if $\gcd\{\ell_1,\dots,\ell_n\}=1$.
\end{cor}
Corollary~\ref{cor:schutzenberger} was obtained by Sch\"utzenberger~\cite{Schutzenberger:1967} by purely combinatorial arguments. However,
the Road Coloring theorem shows more: it implies that one can get a synchronized code from a given maximal prefix code $X$ whose codewords
length are relatively prime simply by relabeling the edges of the automaton $\mathcal{A}_X$. The latter fact was proved by Perrin and
Sch\"utzenberger in 1992~\cite{Perrin&Schutzenberger:1992}, that is, much earlier than the proof of the Road Coloring conjecture in full
generality has been found.
